Embodiments of the inventive subject matter generally relate to the field of evolutionary computing, and, more particularly, to using local and global catastrophes in evolutionary computing.
Software tools employ metaheuristic optimization algorithms to solve optimization problems. Examples of metaheuristic optimization algorithms include evolutionary algorithms (e.g., genetic algorithm, differential evolution), ant colony optimization algorithms, simulated annealing algorithms, etc.
Evolutionary algorithms use techniques loosely based on Darwinian evolution and biological mechanisms to evolve solutions to design problems. A software tool that implements an evolutionary algorithm starts with a randomly generated population of solutions, and iteratively uses sexual recombination, crossover, mutation, and the Darwinian principles of natural selection to create new, more fit solutions in successive generations. Evolutionary algorithms have been deployed in many aspects of research and development, and have generated human-competitive solutions to a wide range of problems. Within International Business Machines Corporation (IBM), (SNAP) has been successfully applied to I/O circuit design for Power?/7+, scan-chain routing, the high performance computing (HPC) bidding process, signal integrity for z-series buses, and compiler flag tuning.
An executing instance of an evolutionary algorithm can prematurely converge. A population of candidate solutions converges when the genes of a few fit candidate solutions quickly dominate the population, and constrain the population to a local optimum. Premature convergence means that the population of candidate solutions for an optimization problem has converged too early, thus delivering a suboptimal result.